//dp[i][j][k]表示，考虑[0, i]个任务，人数j小于等于n，利润k>= minprofit时的所有选法
//如果不选第i个任务, dp[i][j][k] = dp[i - 1][j][k]
//如果不选第i个任务, dp[i][j][k] = dp[i - 1][j - ni][k - pi]
    //因为第三个位置表示的是利润至少为m，如果(k-pi<0)，就说明此时的这一个利润就可以达到最低要求，是合法的
    //但是数组下标为负数，为了解决可以让其去下标0处寻找
    //dp[i][j][k] = dp[i - 1][j - ni][max(0, k - pi)]

//dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - ni][max(0, k - pi)]

// class Solution {
//     uint64_t N = 10e8 + 7;
// public:
//     int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
//         int len = profit.size();
//         vector<vector<vector<uint64_t>>> dp(len + 1, vector<vector<uint64_t>>(n + 1, vector<uint64_t>(minProfit + 1, 0)));

//         //当i = 0，没有任务时并且minprofit为0时，dp[0][j][0] = 1, 表示不选任务，且最低利润为0，有1种选法
//         for (int j = 0; j < n + 1; j++)
//             dp[0][j][0] = 1;

//         for (int i = 1; i < len + 1; i++)
//         {
//             for (int j = 0; j < n + 1; j++)
//             {
//                 for (int k = 0; k < minProfit + 1; k++)
//                 {
//                     dp[i][j][k] += dp[i - 1][j][k];
//                     if (j - group[i - 1] >= 0)
//                         dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];

//                     dp[i][j][k] %= N;
//                 }
//             }
//         }

//         return dp[len][n][minProfit];
//     }
// };

//空间优化
class Solution {
    uint64_t N = 1e9 + 7;
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int len = profit.size();
        vector<vector<uint64_t>> dp(n + 1, vector<uint64_t>(minProfit + 1, 0));

        //当i = 0，没有任务时并且minprofit为0时，dp[0][j][0] = 1, 表示不选任务，且最低利润为0，有1种选法
        for (int j = 0; j < n + 1; j++)
            dp[j][0] = 1;

        for (int i = 1; i < len + 1; i++)
            for (int j = n; j >= group[i - 1]; j--)
                for (int k = minProfit; k >= 0; k--)
                {
                    dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];

                    dp[j][k] %= N;
                }

        return dp[n][minProfit];
    }
};